﻿//2487. 从链表中移除节点
//给你一个链表的头节点 head 。
//移除每个右侧有一个更大数值的节点。
//返回修改后链表的头节点 head 。


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNodes(ListNode* head)
    {
        stack<ListNode*> sta;
        auto p = head;
        while (p)
        {
            int x = p->val;
            while (!sta.empty() && sta.top()->val < x)
            {
                sta.pop();
            }
            sta.push(p);
            p = p->next;
        }
        ListNode* newhead = nullptr;
        while (!sta.empty())
        {
            sta.top()->next = newhead;
            newhead = sta.top();
            sta.pop();
        }
        return newhead;
    }
};